package DP;

/**
 * 扔鸡蛋问题 https://zhuanlan.zhihu.com/p/41257286
 */
public class MiniPathSum {

    /**
     *
     */
    public int minPathSum(int[][] grid) {
        int weight = grid.length;
        if(weight == 0){
            return 0;
        }
        int height = grid[0].length;
        if(height == 0){
            return 0;
        }

        int[][] dp = new int[2][height];
        int old,now=0;
        for(int i=0; i < weight; i++){
            old = now;
            now = 1-now;
            for(int j=0; j < height; j++){
                if(i == 0 && j == 0){
                    dp[now][0] = grid[0][0];
                    continue;
                }

                //顶栏和侧栏，需要一直加
                if(i == 0 ){
                    dp[now][j] = dp[now][j-1] + grid[i][j];
                    continue;
                }
                if(j == 0 ){
                    dp[now][j] = dp[old][j] + grid[i][j];
                    continue;
                }

                dp[now][j] = Math.min(dp[old][j], dp[now][j-1]) + grid[i][j];
            }
        }

        return dp[now][height-1];
    }

    //滚动数组
    public int minPathSum2(int[][] grid) {
        int rows = grid.length;
        if(rows == 0){
            return 0;
        }
        int columns = grid[0].length;
        if(columns == 0){
            return 0;
        }
        //滚动数组
        int[][] dp = new int[2][columns];
        int old,now = 0;
        for(int i=0; i < rows; i++){
            old = now;
            now = 1 - now;//swap 0 --> 1  1 --> 0，注意，最开始now是1，并不是从0开始。
            for(int j=0; j < columns; j++){
                if(i == 0 && j == 0){
                    dp[now][0] = grid[0][0];//这里也要严格用now，不能认为是记录到0了。
                    continue;
                }

                int t = Integer.MAX_VALUE;
                if(i > 0){
                    t = Math.min(t, dp[old][j]);
                }
                if(j > 0){
                    t = Math.min(t, dp[now][j-1]);
                }
                dp[now][j] = t + grid[i][j];
            }
        }

        return dp[now][columns-1];
    }


    public static void main(String[] args){
        MiniPathSum m = new MiniPathSum();
        int[][] a = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(m.minPathSum(a));
        System.out.println(m.minPathSum2(a));

    }


}
